package leecode

func lastStoneWeightII(stones []int) int {
	//将石头尽可能分为两堆相似的,这样两两相撞之后,值最小
	sum := 0
	for i := 0; i < len(stones); i++ {
		sum += stones[i]
	}
	target := sum / 2
	dp := make([]int, 15001) //dp数组 dp[j] 是容量为j的背包, 最多可以装的价值为dp[j]
	for i := 0; i < len(stones); i++ {
		// 背包容量要大于石头重量
		for j := target; j >= stones[i]; j-- {
			dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
		}
	}
	return sum - dp[target] - dp[target]
}
